---

[toc]

数据校验码

1.什么是错误

$1$变成$0$，$0$变成$1$

2.什么样的编码具有检错纠错能力

**码距**：任意两个码字之间最少变化的二进制位数 具有检错纠错能力的数据校验码的实现原理是：在编码中，除去合法的码字，再加进一些非法的码字，当某个合法的码字出现错误时，就变成非法码字 **对于码距≥2的数据校验码，开始具有检错能力，码距越大，检、纠错能力就越强，而且检错能力总大于或等于纠错能力**

3.如何发现错误

奇偶校验码

校验位的取值（0或1）将使得整个校验码中”1”的个数为奇数或偶数：

1. 奇校验——使得整个校验码中”1”的个数为奇数
2. 偶校验——使得整个校验码中”1”的个数为偶数
3. 交叉奇偶校验：传送数据块时，不仅每个字节有一个奇偶校验做横向校验，而且全部字节的同一位也设置一个奇偶校验做纵向校验

例如，对于二进制数1000011，奇校验码为10000110，偶校验码为10000111

判断是否出错：E=校验码各位的异或得到的结果；对于奇校验E=1时编码正确，而偶校验则是E=0时编码正确 纠错能力：奇偶检验只能发现奇数个位的错误，不能定位出错点 ## 4. 如何确定错误的位置 ### 海明校验码 校验位K，信息位N，则$2^{K+1} \ge N+K+1 $ (1)编码 一个字节由8位二进制位组成，此时N=8， K=5，故海明码总位数为N+K=13，表示为：$H_{13}\ H_{12}...H_{2}\ H_{1}$ 五个校验位$P_5~P_1$对应的海明码位为:$H_{13}、H_{8}、H_{4}、H_{2}、H_{1}$,除$P_5$外其余四位满足$P_i中i等于2^{i-1}$的关系，而$P_5$只能放在$H_{13}$

P_1校验的是$D_1、D_2、D_4、D_5、D_7$，对应的海明码为$H_1(1),H_5(4+1),H_7(4+2+1),H_9(8+1),H_{11}(8+2+1)$,化位二进制就会发现，都有一个$XXXXXXX1$的形式，也就是说$P_i$校验的是二进制中权值为i的位数值为1的那些位数$(D_{位数})$,P2,P3,P4,P5同理 则$P_1=D_1\oplus D_2\oplus D_4\oplus D_5\oplus D_7$，用同样的方法将其他$P_i$求出 (2)校验 将接收到的海明码按如下关系进行偶校验： 如右所示：$S_1=P_1\oplus D_1\oplus D_2\oplus D_4\oplus D_5\oplus D_7$ ，即将$P_1$和对应的$D_i$进行异或算出结国 然后依次求出$S_2\ S_3\ S_4\ S_5$

① 如果$S_5 \sim S_1为00000$时，表明无错

② 如果$S_5 \sim S_1$仅有一位不为$0$，表明是某一位校验位出错或三位海明码同时出错 ③ 如果$S_5 \sim S_1 $有两位不为$0$，表明是两位海明码同时出错，但无法确定出错位置

④ 如果$S_5 \sim S_1$有三位不为$0$，表明是一位信息位出错或三位校验位同时出错，出错位置由$S_4 \sim S_1 $四位编码指明